var ans [][]string

func solveNQueens(n int) [][]string {
    ans = make([][]string, 0)
    chessBoard := make([][]string, n)
    for i, _ := range chessBoard {
        chessBoard[i] = make([]string, n)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++{
            chessBoard[i][j] = "."
            
        }
    }
    backTracking(n, 0, chessBoard)
    return ans
}

func backTracking(n, row int, chessBoard [][]string) {
    if n == row {
        tem := make([]string, n)
        for i:=0; i<n; i++ {
            tem[i] = strings.Join(chessBoard[i], "")
        }
        ans = append(ans, tem)
        return
    }
    for col:=0; col<n; col++ {
        if checkChessBoard(row, col, chessBoard) {
            chessBoard[row][col] = "Q"
            backTracking(n, row+1, chessBoard)
            chessBoard[row][col] = "."
        }
    }
    
}

func checkChessBoard(row, col int, chessBoard [][]string) bool {
    n := len(chessBoard)
    // 列判断
    for i:=row; i>=0; i-- {
        if chessBoard[i][col] == "Q" {
            return false
        }
    }
    // 45°判断
    for i, j := row, col; i>=0 && j<n; i, j = i-1, j+1 {
        if chessBoard[i][j] == "Q" {
            return false
        }
    }
    // 135°判断
    for i, j := row, col; i>=0 && j>=0 ; i, j = i-1, j-1{
        if chessBoard[i][j] == "Q" {
            return false
        }
    }
    return true
}